1. Field of the Invention
The present invention relates to a real-time system which executes a plurality of periodic tasks in a plurality of processors by real-time scheduling.
2. Description of the Related Art
A real-time system is a computer system which is constrained by time, i.e., “the process of a task must be completed within a time limit set for the task”. In general, a time limit set for each task is called “deadline”, and incompletion of a task process by the deadline is called a “deadline miss”. A deadline miss should not occur in real-time systems.
Typical examples of the real-time system are an air traffic control system, plant control monitoring system, and medical system. For example, the air traffic control system sets a safety interval between aircrafts and between an aircraft and an obstruction in order to avoid any crash. Given a task of determining whether airplanes will collide with each other within 1 sec, a 2-sec task process is useless. The air traffic control system must run under severe time constraints.
Operating a device under severe time constraints for inhibiting any deadline miss is called “real-time scheduling”, which includes the following two methods:
1. a scheduling method
2. a real-time schedulability determination method
The scheduling method will be explained first. A task typified by “a process of detecting a collision of an airplane” is executed by a finite number of processors mounted on the real-time system. Since one processor can process only one task at once, when there are a plurality of tasks to be processed by the real-time system, these tasks are shared in time division between a finite number of processors, and a timing, a processor, and a task to be executed are scheduled. This method will be called a scheduling method in this specification.
The real-time schedulability determination method will be explained next. In order to operate the real-time system under severe time constraints for inhibiting any deadline miss, tasks which exceed the performance of the system must not be accepted. For this reason, when a set of tasks and a scheduling method are given and the given tasks are scheduled by the scheduling method, the real-time system determines whether the time constraints of all the tasks can be observed (whether a deadline miss occurs or not), and decides tasks to be accepted by the system on the basis of the determination results. This determination method will be called a real-time schedulability determination method.
Whether the time constraint of a task can be observed depends on the task and at the same time on the scheduling method. When the total performance necessary to execute tasks is much lower than the performance of the real-time system, the system can execute tasks without any deadline miss in most cases regardless of the scheduling method. To the contrary, if the total performance necessary to execute tasks exceeds the performance of the real-time system, the system cannot prevent a deadline miss by any scheduling method. However, when the total performance necessary to execute tasks is equal to or slightly lower than the performance of the real-time system, the scheduling method decides whether the system can execute tasks without any deadline miss or a deadline miss occurs. To cope with these two cases, according to the real-time schedulability determination method, two inputs, i.e., a set of tasks and a scheduling method are input, and the result of determining whether real-time scheduling is possible or impossible is returned.
If a request to release a new task arrives at the real-time system, the system performs the following procedures. First, the system determines whether the time constraints of the new task and all tasks in execution in the real-time system can be observed by the scheduling method (no deadline miss occurs) when the new task is accepted. If so, the real-time system accepts release of the new task.
Second, the real-time system schedules the new task and all tasks in execution in the real-time system by using the scheduling method, and executes the tasks in accordance with the scheduling results.
In the scheduling method, it is important to assign proper processors to proper tasks in a proper period so as to execute each task without causing any deadline miss. Task execution free from any deadline miss is implemented by scheduling a processor used for each task so as to end the process of the task by the time limit.
A concrete example of a periodic task scheduling method is an EDF (Earliest Deadline First) algorithm (see, e.g., reference 1). The EDF algorithm is an algorithm of preferentially assigning a processor to a task of an early deadline at an early time.
A known example of the real-time schedulability determination method is a method of determining whether real-time scheduling is possible by the EDF algorithm (see, e.g., reference 2).
Another known example of the real-time schedulability determination method is a method of virtually scheduling tasks by actually using the scheduling method, and checking whether no deadline miss occurs in all the cycles of tasks (see, e.g., reference 3).
The determination method described in reference 2 assumes that the number of processors simultaneously assignable to one task is one, and does not consider a task which simultaneously requires a plurality of processors. Some tasks simultaneously require a plurality of processors in order to increase the process efficiency. Hence, a schedulability determination method available even when a plurality of processors need be simultaneously assigned to one task must be provided. Also, the determination method described in reference 2 may determine that real-time scheduling is impossible though real-time scheduling is actually possible, and the determination precision of this method is low.
The method of virtually scheduling tasks by actually using the scheduling method, and checking whether no deadline miss occurs in all the cycles of tasks takes a long calculation time for determination and is not practical.
Conventionally, when a plurality of periodic tasks are executed by a plurality of processors, it cannot be accurately determined at a high speed whether real-time scheduling is possible.
The present invention has been made to overcome the conventional drawbacks, and has as its object to provide a schedulability determination method capable of accurately determining at a high speed whether a plurality of periodic tasks can be scheduled in real time on a plurality of processors, and a real-time system using the method.
[Reference 1] J. W. S. Liu, “Real-Time Systems”, Prentice Hall, 2000
[Reference 2] T. P. Baker, “An Analysis of EDF Schedulability on a Multiprocessor”, FSU Computer Science Technical Report TR-030202, 2003
[Reference 3] J. F. Hermant et al., “Real-Time Fixed and Dynamic Priority Driven Scheduling Algorithms: Theory and Experience”, Inria Technical Report, 1996